package problem69_Sqrt;

public class MySolution {
	public int mySqrt(int x) {
		int low=1,high=x/2+1;
		while(low<=high){
			long mid=(low+high)/2;
			long mul=mid*mid;
			if(mul==x)
				return (int)mid;
			else if(mul>x)
				high=(int)mid-1;
			else
				low=(int)mid+1;
		}
		return high;
    }
	
	public static void main(String[] args){
		System.out.println(new MySolution().mySqrt(2147395599));
	}
}
